/* Universidad del Valle de Guatemala
 * Facultad de Ingenieria
 * Departamento de Ciencias de la Computacion
 * Algoritmos y estructura de Datos
 * David Coronado, 07325
 * HuffmanBinaryTree
 *      implementacion de arboles binarios con la codificacion de Huffman
 */

public class HuffmanBinaryTree {

	public Node first, last;
	public Node root;
	public byte tabla[][];
	public String codeList[];
	private int size;
	private int cont;

	public HuffmanBinaryTree(Node primero){
		size=0;
		cont=0;
	}
	/**
         * Agrega un nuevo elemento (nodo) al arbol
	 * @param nn elemento a añadir
	 */
        
	public void agregarElemento(Node nnodo){
		if(first==null){
                    first=nnodo;
                    last=nnodo;
		}
		else{
			Node aux=first;
			while(aux.getRight()!=null)
				aux=aux.getRight();
			aux.setRight(nnodo);
			nnodo.setLeft(aux);
			last=nnodo;
		}
		size++;
	}
        
	/**
	 * Ordena la lista enlazada de nodos por medio de su frecuencia de menor
	 * a mayor
	 *
	 */
	public void ordenar(){

		Node aux1=first;
		Node aux2=aux1;
		int tempFrec;
		char tempLetra;

		while(aux1!=null){

			while(aux2.getRight()!=null){
				if(aux2.getFrecuency()>=aux2.getRight().getFrecuency()){
					tempFrec=aux2.getFrecuency();
					tempLetra=aux2.getCharac();
					aux2.setFrecuency(aux2.getRight().getFrecuency());
					aux2.setCharac(aux2.getRight().getCharac());
					aux2.getRight().setFrecuency(tempFrec);
					aux2.getRight().setCharac(tempLetra);

					if(aux2.getCharac()>aux2.getRight().getCharac() && aux2.getFrecuency()==aux2.getRight().getFrecuency()){
						tempFrec=aux2.getFrecuency();
						tempLetra=aux2.getCharac();
						aux2.setFrecuency(aux2.getRight().getFrecuency());
						aux2.setCharac(aux2.getRight().getCharac());
						aux2.getRight().setFrecuency(tempFrec);
						aux2.getRight().setCharac(tempLetra);
					}
				}
				aux2=aux2.getRight();
			}
			aux2=first;
			aux1=aux1.getRight();
        }
	}
        
	/**
	 * Genera el arbol de Huffman con los codigos
	 */
        
	public void generarArbol(){

		Node aux=first, temp;
		tabla=new byte[size][3];
		codeList = new String[size];
		int peso=0;

		while(aux.getRight()!=null){
			if(aux.getRight()!=null)
				peso=aux.getFrecuency() +  aux.getRight().getFrecuency();
			else
				peso=aux.getFrecuency();

			temp=new Node((char)0, peso, false);
			temp=ubicarNodo(temp, aux);
			temp.setLeftSon(aux);
			temp.setRightSon(aux.getRight());
			aux=aux.getRight().getRight();

			if(aux.getRight()==null)
				root=temp;
		}
		generarCodigo(root, "");
	}

	/**
	 * Ubica un nodo en el arbol
	 * @param nodo a ubicar
	 * @param aux2 es el nodo inicial
	 * @return el nodo ubicado
	 */
        
	public Node ubicarNodo(Node nodo, Node aux2){
		Node aux=aux2;

		while (aux!=null) {
			if(nodo.getFrecuency()<=aux.getFrecuency()){
				aux.getLeft().setRight(nodo);
				nodo.setLeft(aux.getLeft());
				aux.setLeft(nodo);
				nodo.setRight(aux);
				return nodo;
			}
			if(aux.getRight()==null){
				aux.setRight(nodo);
				nodo.setLeft(aux);
				last=nodo;
				break;
			}
			aux=aux.getRight();
		}
		return nodo;
	}

	/**
	 * Genera el codigo huffman del arbol
	 * @param nodo es la raiz del arbol
	 * @param cadena es la cadena de codigo
	 */
	public void generarCodigo(Node nodo, String cadena){

		if(nodo!=null){
			if(nodo.isType()){
				nodo.setCode(cadena);
				tabla[cont][0]=(byte)nodo.getCharac();
				tabla[cont][1]=(byte)nodo.getFrecuency();
				codeList[cont] = cadena;
				cont++;
			}
			generarCodigo(nodo.getLeftSon(), cadena +"0");
			generarCodigo(nodo.getRightSon(), cadena +"1");
		}
	}

	/**
	 * Permite obtener el codigo huffman
	 * @param Es el numero que se desea saber su codigo huffman
	 * @return el codigo huffman en formato String
	 */
	public String getCodigo(byte value){

		for(int i=0; i<size; i++)
			if(tabla[i][0]==value ){

                           // System.out.println((char) valor + " - " + listaCodigos[i]);
                            return codeList[i];
                        }
		return null;
	}


	/**
	 * @return la tabla de las frecuencias
	 */
	public byte[][] getTabla() {
		return tabla;
	}
	/**
	 * @return un entero, representando el numero de nodos del arbol
	 */
	public int getTamano() {
		return size;
	}

}
